Pastry

标签

分布式/P2P 与路由

字数

5079 字

阅读时间

20 分钟

Pastry（Middleware 2001）是这批四篇里第一次把"逻辑跳与物理跳不一致"当成一等公民来处理的一篇。它和 Chord 解决同一个问题（给定 key 找到 nodeId 最接近的节点），但选的路完全不同：按前缀逐位逼近，而不是按数值差逼近环。

按地址前缀路由这件事并非它首创，它的增量落在三件事上：

Pastry 与 Tapestry 和 Plaxton 等人的工作、以及 landmark 层次路由有些相似。基于地址前缀的路由（可以看作超立方路由的推广）是这些方案的共同点。然而，Plaxton 与 landmark 方案都不是完全自组织的。

所以 Pastry 的增量落在三件事上：自组织、显式追求网络邻近性、以及对复制的支持。它定位成一个通用底座，当时已经在其上建成的有 PAST（全局持久存储）与 SCRIBE（可扩展发布订阅）。

标识符：随机分配带来一个非显然的好处

每个节点被分配一个 128 位 nodeId，取值空间是一个从 $0$ 到 $2^{128}-1$ 的环形 nodeId 空间。nodeId 在节点加入时随机分配（例如对节点的公钥或 IP 地址做密码学哈希），并假定这组 nodeId 在 128 位空间中均匀分布。

随机分配有一个直接后果，它是后面很多设计的前提：

由于 nodeId 是随机分配的，以高概率，nodeId 相邻的节点在地理位置、归属、司法管辖、网络接入等方面是多样的。

这句话反过来用的地方在后面：因为相邻 nodeId 在地理上分散，所以"查一个 key"不能就近服务 —— 于是需要一个启发式把查询导向离客户端近的那个副本（见后面的 k 副本一节）。

三层状态

结构	内容	用途
routing table $R$	${\log }_{2^b}N$ 行、每行 $2^b-1$ 项	路由主力
neighborhood set $M$	按 proximity metric 离自己最近的 $|M|$ 个节点	正常不参与路由，用于维持邻近性
leaf set $L$	$|L|/2$ 个 nodeId 最接近且较大的 + $|L|/2$ 个最接近且较小的	路由的收尾段

routing table 的第 $n$ 行那 $2^b-1$ 项，指向的是与前缀长度 $n$ 位相同、但第 $n+1$ 位取遍其余 $2^b-1$ 个可能值的节点。每一项里具体放哪个节点，选的是按 proximity metric 离自己最近的那个 —— 这一条就是邻近性的来源。

$b$ 的取舍是全篇最干脆的一组数字：表大小约 ${\log }_{2^b}N\times (2^b-1)$ 项，最大跳数 ${\log }_{2^b}N$。于是

$b$	节点数	路由表平均项数	期望跳数
4	${10}^6$	约 75	5
4	${10}^9$	约 105	7

$|L|$ 与 $|M|$ 的典型取值是 $2^b$ 或 $2\times 2^b$（实验里用 $|L|=16$、$|M|=32$，对应 $b=4$）。

路由算法：两条规则 + 一个罕见情形

nodeIds 与 keys 都被看作 $2^b$ 进制的一串数字。每一步：

1. 先看 key 是否落在自己 leaf set 覆盖的 nodeId 范围里（即 $L_{-|L|/2}\le D\le L_{|L|/2}$）。若是，直接转发给 leaf set 里离 key 最近的那个节点（可能就是自己），路由结束；
2. 否则用 routing table：设 $l$ 是 key 与当前 nodeId 的共享前缀长度（以数字计），若 $R[l][D_l]$ 非空就转给它 —— 这一步保证前缀比当前节点多匹配至少一位；
3. 罕见情形：那一项为空、或对应节点不可达时，转而转发给"与 key 的共享前缀至少与本地一样长、且数值上更接近 key"的节点。这样的节点必定在 leaf set 里，除非消息已经到了数值上最接近 key 的节点。

第 3 种情形出现的概率与 $|L|$ 有关：$|L|=2^b$ 时，一次消息传输中出现该情形的概率小于 0.02；$|L|=2\times 2^b$ 时小于 0.006，且此时以高概率最多只多一个路由步。

一个诚实的边界：大量节点同时失败、而各节点还在更新状态时，所需路由步数最坏可能是 $N$ 的线性。这是个很松的上界，实测里性能是随近期失败数逐渐退化的。

加入：三层分别从哪里来

新节点 $X$ 需要先知道一个按 proximity metric 离自己近的、已经在系统中的节点 $A$（可以靠 expanding ring IP 组播自动找到，或由管理员从外部渠道给）。然后 $X$ 请 $A$ 路由一条 key 等于 $X$ 的特殊 "join" 消息，这条消息会到达nodeId 数值上最接近 $X$ 的现有节点 $Z$。

$A$、$Z$、以及 $A$ 到 $Z$ 路径上遇到的所有节点，都把自己的状态表发给 $X$，$X$ 据此初始化：

• neighborhood set 取自 $A$（因为 $A$ 就在 $X$ 附近）；
• leaf set 以 $Z$ 的叶集为基础（因为 $Z$ 的 nodeId 最接近 $X$）；
• routing table 逐行来：第 0 行的项与节点自身 nodeId 无关，所以 $A$ 的第 0 行对 $X$ 也适用；第 1 行取自路径上第一个节点 $B$ —— 理由是 $X$ 与 $B$ 的第一位数字相同，所以 $B_1$ 与 $X_1$ 的项共享同一前缀；第 2 行取自路径上再下一个节点 $C$，依此类推。

最后 $X$ 把自己算出的状态发给它的 neighborhood set、leaf set 与 routing table 里出现的每个节点，这些节点再据收到的信息更新自己。一次加入的消息总代价是 $O({\log }_{2^b}N)$，常数约为 $3\times 2^b$。

并发加入/离开用的是乐观方式：提供状态时附一个时间戳，接收方基于它调整自己的状态、之后回一条更新消息并原样带回那个时间戳，于是提供方可以检查自己的状态是否已变；变了就回一份新状态，接收方重做一遍。理由是一个节点的加入/离开只影响系统中很小一部分节点，所以竞争很少。

route locality：两条事实与一句总结

要维持的性质是：routing table 的每一项都指向"在所有符合该项前缀要求的存活节点里、按 proximity metric 离本节点最近"的那个。邻近性度量是一个标量（IP 路由跳数、地理距离等），由应用提供一个函数来算出某个 IP 地址相对自己的"距离"，值越小越可取；这个 proximity 空间被假定为欧氏的（三角不等式成立）；要注意 IP 跳数在实际中并不满足三角不等式 —— 此时 Pastry 的基本路由不受影响，但路由的邻近性可能变差，量化其影响列为后续工作。

两条支撑路由质量的事实：

1. 若一条消息从节点 $A$ 以距离 $d$ 路由到节点 $B$，那么它之后不可能再被路由到"距 $A$ 小于 $d$"的节点（在路由表准确的前提下，直接由路由过程推出）；
2. 每一步的期望行进距离是指数增长的 —— 因为第 $l$ 行的项是从一个大小为 $N/2^{bl}$ 的集合里挑的，逐行取自指数递减的集合；在 nodeId 随机均匀分布的前提下，每一行里最近的那一项的期望距离就随之指数增长。

两条合起来：

虽然不能保证消息与源点的距离每一步都单调增加，但消息倾向于迈出越来越大步，且不可能回到路径上任何节点 $i$ 的 $d_i$ 距离之内（$d_i$ 是它离开节点 $i$ 这一跳的距离）。所以这条消息无处可去，只能朝着目的地走。

第二阶段的补强

第 0 行取自 $A$ 是没问题的（$A$ 近 $X$、$A$ 的第 0 行项近 $A$、由三角不等式它们也离 $X$ 不远）。但第 1 行取自 $B$，而 $B$ 未必离 $X$ 近 —— 这里"直觉上看起来不保持目标性质"，而上面的指数递减论证解释了为什么 $B_1$ 对 $X_1$ 其实是个合理的取值。

因为这只是近似，为了避免误差级联下去导致路由邻近性持续变差，还有第二个阶段：$X$ 向它 routing table 与 neighborhood set 里的每个节点索取状态，比较对应项的远近，发现自己更近的节点就更新自己的状态。其中 neighborhood set 提供的信息很有价值，因为它维护并传播的是"附近节点"的信息，与 nodeId 前缀无关。

三种方式的对照实验（5,000 个节点逐个加入）：

方法	做法
Pi	假想做法：只从路径上每个节点取对应的那一行
WT	取路径上每个节点的完整状态，但不从这些项里去再取状态（等于省掉第二阶段）
WTF	Pastry 实际用的方法：第一阶段之后再从表里出现的每个节点取状态

结论是 WTF 效果好得多：平均每层只有不到 1 项不是最优；而"在节点加入过程中少交换信息，会以路由表邻近性质量急剧下降为代价"。

定位 k 个副本里最近的那个

有些应用（如 PAST）把信息复制在nodeId 数值上最接近某个 key 的 $k$ 个节点上。Pastry 天然会把消息路由到数值上最接近 key 的存活节点，只要 $k$ 个里还有一个活着，消息就能到其中一个。

这里暴露出前缀路由的一个结构性缺陷：

最坏情况下，$k/2-1$ 个副本会存放在"nodeId 在第 0 层域上与 key 不同"的节点上。 于是 Pastry 会先朝剩下那 $k/2+1$ 个节点里最近的一个路由。

补救是一个启发式：用本地信息估计 nodeId 空间里其他节点 leaf set 的覆盖密度，据此探测消息是否已经接近那 $k$ 个最接近的节点，然后切换到按数值最近地址路由，去找最近的副本。

实测（$b=3$、$|L|=8$、10,000 节点、100,000 次查找）：

配置	命中最近的节点	命中最近两个之一
标准加入（WTF）、无启发式	68%	87%
加上启发式	76%	92%
完美估计（理想化的启发式上界）	约 78%	约 94%

启发式只比"完美估计"这个理论上限差约 2%。 而用 Pi / WT 这两种省消息的加入方式，定位附近节点的能力下降明显。

故障与修复

节点被认为失败，判据是它在 nodeId 空间中紧邻的邻居已无法与它通信。

• leaf set 的修复：某邻居向失败节点那一侧索引最大的存活节点索取叶集（例如 $L_i$ 失败、$-|L|/2<i<0$，就向 $L_{-|L|/2}$ 要）。收到的叶集与本地叶集部分重叠、并含本地没有的邻近 id；从中选出合适的那个，并联系它来确认它确实活着，才插进 $L$。这保证除非 $|L|/2$ 个 nodeId 相邻的节点同时失败，每个节点都能惰性地修好自己的叶集；而由于相邻 nodeId 的多样性，这种同时失败即便在适中的 $|L|$ 下也极不可能。
• routing table 项的修复：先联系同一行另一个项 $R[i][l],i\ne d$ 所指的节点，问它那一项；若该行没有任何项指向符合前缀的存活节点，就转而联系 $R[i][l+1]$，"撒一张更大的网"。
• neighborhood set 的维护：周期性联系每个成员验活；有成员不响应就向其它成员索取它们的 neighborhood table，逐个算距离并据此更新自己的集合。

任意失败与网络分区

上面的机制都假设节点静默失败，非静默的情形另有一节：

Pastry 的路由方案是确定性的，因此它容易受到"接收消息但不正确转发"的恶意或失败节点的攻击。重复的查询可能每次都失败，因为它们通常走同一条路。

缓解手段是把路由随机化：在满足"前缀更长、或前缀等长但数值更近"这一约束的多个候选里随机选一个（实践中概率分布应偏向最优选择以保证平均延迟低），恶意节点在路径上时客户端重试若干次即可绕开。

另一类麻烦是 IP 路由异常（某些主机之间不可达）。Pastry 对此是容忍的 —— 只要节点还能与它在 nodeId 空间的紧邻邻居通信，它就被视为存活且在覆盖网中可达。但这带来一个新的隐患：IP 路由故障期间，Pastry 的自组织协议可能造出多个相互隔离的 Pastry 覆盖网；而由于 Pastry 的自组织几乎完全依赖覆盖网内部的信息交换，这些孤立覆盖网可能在 IP 连通性完全恢复之后依旧存在。 解法是让节点周期性地用 expanding ring 组播搜索附近的 Pastry 节点（随机、低频、限制在有限的 IP 跳数范围内、且附近节点近期没搜过），孤立覆盖网最终会被发现并重新并入。

评测

原型用 Java 实现，另做一个网络模拟环境，支持到 100,000 个 Pastry 节点。硬件是一台四路 Compaq AlphaServer ES40（500MHz 21264、6 GB 内存、Tru64 UNIX 4.0F）。所有节点跑在同一个 Java VM 里 —— 这对实现基本透明，Java 运行时会自动把节点间通信降为本地对象调用。

模拟网络给每个节点在平面上随机取一个坐标（范围 $[0,1000]$），并维护节点间距离。这里有一个很直的自我限定：

Internet 中的节点并不是均匀分布在欧氏空间里的；相反存在强烈的聚集，且三角不等式并不总是成立。 我们正在基于一个更真实的拓扑模型做模拟；早期结果显示 Pastry 与邻近性相关的路由性质并没有被这个改变显著影响。

路由跳数

节点数从 1,000 到 100,000，$b=4$、$|L|=16$、$|M|=32$，200,000 次随机节点对之间的路由。跳数随规模的增长与预测一致；10 万节点时最大路由长度就是 ${\log }_{2^b}\mathrm{100,000}=5$。跳数分布（10 万节点、20 万次查找）在 4 跳处是峰值（0.6449），3 跳 0.1643、5 跳 0.1745，两端 0 与 6 都趋近于 0。

路由距离：与"完整路由表"对照

把 Pastry 沿路走过的距离（相邻节点间距离之和）与一个假想的、维护完整路由表的方案（距离即源到目的地的直线距离）对照，结果归一化到后者：

Pastry 的路由只长约 30% 到 40%。 考虑到 Pastry 的路由表只有约 ${\log }_{2^b}N\times (2^b-1)$ 项，这个结果相当好。10 万节点时 Pastry 的路由表约 75 项，而完整路由表要 99,999 项。

另外，未经优化的 Java 实现每秒能处理 3,000 条以上消息，说明路由过程很轻。

故障恢复

5,000 节点、$b=4$、$|L|=16$、$|M|=32$、$k=5$，随机选 10%（500 个）节点静默失败，然后做 20 万次查找（先关掉修复设施、再打开修复设施各一轮）：

状态	平均跳数
无失败	2.73
失败、不修复路由表	2.96
失败、修复路由表	2.74

不修复时陈旧的表状态导致路由质量显著退化，而修复后平均跳数只比失败前略高。修复能把所有缺失的表项补回来，邻近性质量也接近失败前（第 0 行"最优项"的平均数比失败前少约 1 项，但次优项与最优项之间的实际距离非常小，这在直觉上也合理，因为第 0 行项的期望距离本来就很近）。另外两点口径要记：Pastry 是惰性修复的 —— 只有在表项被用到时才修，所以为了隔离修复效果，统计时排除了那 20 万次查找中从未被用到的表项；而失败后第 1、2 层"空项"增多，原因是节点总数减少、使上层表项变稀疏，不是表质量下降。

修复代价：平均每个失败节点需要 57 次远程过程调用才能修好所有相关表项。

相关

• Chord —— 最直接的对照：Chord 不按"共享越来越长前缀"路由，而按与目标地址的数值差转发；并且**"与 Pastry 和 Tapestry 不同，Chord 没有为获得好的网络邻近性做任何显式努力"**。这正好解释了为什么两篇的"扇出结构"不同（finger 指 $2^{i-1}$ 之后的节点 vs. 路由表按第 $n+1$ 位展开）
• CAN —— 另一条对照线：CAN 在 $d$ 维空间里路由、每节点 $O(d)$ 项、$O(d{N}^{1/d})$ 跳；与 Pastry 的区别是**"路由表不随网络规模增长，但跳数增长快于 $\log N$"**
• Kademlia —— 同为前缀/位路由的一族，但 Kademlia 把度量换成 XOR，并且把路由表组织成二叉树而不是按位展开的二维表；值得连着读它们对"邻居选择"的不同处理
• 一致性哈希算法 —— Pastry 没有显式说自己在用一致性哈希，但它同样把 key 与节点映射进同一个标识符空间并让 key 落在最近的节点上。差别在于 Pastry 额外把邻近性塞进了"最近"这个选择里
• Dynamo —— 对照点在于副本与就近读取的动机相同、手段不同：Dynamo 用偏好列表 + 协调节点让读请求可落到副本，Pastry 用路由过程中的邻近性 + 一个密度启发式让查询先到达离客户端近的副本（两者都在处理"相邻标识符的节点在地理上分散"这个由随机分配带来的后果）

参考

• A. Rowstron, P. Druschel. Pastry: Scalable, Distributed Object Location, and Routing for Large-Scale Peer-to-Peer Systems. Middleware 2001, LNCS 2218.

贡献者

YJ

文件历史

最后编辑于 2 天前查看完整历史

ae1ee-docs：内容完善

448f1-分布式